In a nutshell,
multirate signal processing addresses the question of; how to change the
underlying sampling rate of a discrete time sequence entirely in the
discrete time domain. Consider the following scenario. You have an input signal x of t, and you convert this into
a discrete time sequence via a sampler at
a sampling rate of T1. We will denote the
discrete time sequence as x_T1 of n to express the dependence
on the sampling period. Now, if you change
the sampling period, you will get a different
type of sequence. So here's the question. Given a sample
sequence x_T1 of n, can we build a
discrete time machine that produces another sequence, let's call it x_T2 of n, once we know the relationship
between T1 and T2? In multirate signal processing, we will address two scenarios. The first is when T1
is a multiple of T2, and the second one is when
T2 is a multiple of T1, where N and n are integers. In the first case,
the second sequence will be faster than
the first one, so we will increase the number
of samples per second. In the second case,
we will have to reduce the number of
samples per second. But in reality,
the actual physical values of T1 and T2 are immaterial, all that matters is
their relationship. In the first case as we will see, we will simply output capital N points in the new sequence for
each input sample. In the second case,
we will discard capital N minus one input points, for every output sample. Let's start with the easier case, in which we increase
the number of samples. This is called upsampling, and we can create
an upsample sequence from any discrete time sequence, simply by building
a sequence where we output one sample of the original sequence followed by capital N minus 1 new samples. What do we put in
this new samples? Well, we don't know yet. So for now, let's just put zeros. The upsample sequence
indicated by x_NU of n where capital N here
is the upsampling factor, will be equal to a sample
from the original sequence, when the index is a multiple of capital N,
and zero otherwise. Graphically, we indicate
the upsampling operator with a circle containing
the upsampling factor, and an arrow pointing up. Let's look at an example. Assume this is
the original sequence, of course you know it's
an infinite sequence, so it continues
outside of the plot, to build an upsample sequence
by a factor of four, we take each sample in turn
the original sequence, we output it, and we
follow it by three zeros. The result is
something like this. So you see here
the indexing has changed. The values remain the same, but their indexes
are now different. This is 0, 1, 2, 3, 4, 5, 6, 7, 8, and so on so forth. So all multiples of four are points that belong
to the original sequence, all the others are zeros. What is the spectral
representation of an upsample sequence? This is very easy
to find if we use the z-transform as a first step. So we write the z-transform
of the upsample sequence, and this is a standard summation that defines a z-transform, but now we know that in this sum, only one term out of
n will be non-zero. So we can simplify this sum here by using
a change of variable, and by eliminating
old zero terms in this sum, we end up with
this summation for k that goes to minus
infinity to infinity, of x of k. So samples of
the original sequence times z to the power of
minus capital Nk. So this is the z-transform of the original sequence
computed in z to the power of capital N. If we restrict the z-transform
to the unit circle, to find the Fourier transform, we have that the spectrum of the upsample sequence is simply the spectrum of
the original sequence, where we have contracted
the frequency axis by a factor of capital N.
So what used to be, say the minus pi pi interval, will become the minus Npi to Npi. We can see this graphically. Here in the top plot, we show the spectrum of
the original sequence. Now, in multirate signal
processing is fundamental to remember that discrete times
spectra r to pi periodic. To make that more explicit, we can show the same spectrum
over a larger interval. So here we have the classic two
pi periodic pattern for discrete time spectrum. As I said, the interval
minus pi pi, will now be contracted, so that it will include the
minus two pi two pi interval. This will be mapped to the minus pi pi interval
in the upsample sequence. So the result is Bactrim before the upsample sequence,
will be this one. Let's change the upsampling
factor to get a better feel for what upsampling does
in the frequency domain. Same pattern here,
original spectrum. Original spectrum showed
over a larger interval, and now we're
upsampling by three. So it will be this interval here, that will be mapped onto the minus pi pi interval
in the upsample spectrum, and it will look like so. In general, for an upsampling
factor of capital N, you will have capital N copies
of the original spectrum pulled in the minus
pi pi interval for the new upsample sequence. If n is odd as in this case, you will have
three neat copies like so, and if n is even like in
the previous example, you will have one full copy plus one-half here
and one-half there. Let's look at
another example with slightly different spectral
shape that is not full band, and an upsampling factor of four. Again, the periodicity made
explicit looks like so, and when we upsample by four, we will take the minus four
pi to four pi interval, and map it to minus pi pi, to obtain this spectrum here. Again, sampling factor
is even so you'll have three copies of the spectrum plus one-half here and
one-half here for a total of four copies brought in
the minus pi pi interval. Okay. So we have created
an upsampling machine, that fulfills the basic
requirement of outputting capital N samples for
every input sample. But the result, we don't really like for
a couple of reasons. In the time domain, the signal
doesn't look natural. You have one non-zero
sampled then followed by a run
of zeros samples. This is not a signal you
would find in nature. Similarly, in
the frequency domain, we have this extra copies of the spectrum that are
brought in the band. We don't like that. That's
extra spurious content that we want to eliminate. Now, the cool thing is that the two problems are
exactly one and the same. To understand why that is so, let's look again at
the upsampling problem. Let's take the same
signal as before, but now we're looking at
it over a larger interval. So we can see that
the signal is smooth. Now, we upsample it, say by a factor of four, and let's focus on
the smaller region of this smooth signal. So we start with this. We upsample, and we
introduced this zeros. Now, the signal is
no longer smooth. Because it jumps from non-zero to zero,
every four samples. How can we make it smoother? I'll suppose that instead
of inserting zeros, what we do is repeat the previous non-zero
samples three times. The resulting signal
looks like so. So we repeat
each sample four time, and we got a signal that, although still a
little bit blocky, certainly looks better than jumping back to zero
every four samples. How can we obtain this? Well, it's a simple case of zero-order hold
interpolation done in the discrete time domain. We take our signal, we do the standard upsampling
where we insert zeros, and then we convolve this with the impulse response of the discrete time
zero-order hold, that looks exactly like so. Four ones, from zero to three. Of course for a generic
upsampling factor of capital N, we will use a zero-order
interpolator, whose impulse response
is equal to one for n that goes from zero to
capital N minus one. In the frequency domain,
the response of this filter is well-known, we've studied before, and for capital N equal to four is
shown in this picture here. So you'll have a low pass characteristic that as
you can already foresee, will help us eliminate
the copies of the spectrum that are brought in the minus pi pi interval. We will see that in a second. But first, let's consider
what happens if we want an even smoother upsample signal. As per usual, the next step
in smoothness, is moving from the zero-order
hold interpolator, to the first-order interpolator. Which as you remember, corresponds to connecting
the dots in the output signal. In discrete time, this is
exactly the same thing. So we will get
a signal is like this, although it appears
very very smooth. If you look closely, you will see that
the intermediate samples in the upsample sequence, are simply a linear interpolation between the two
neighboring samples. We know how to obtain this. It's simply the convolution of the standard upsample sequence
where we insert zeros, with a first-order interpolator, whose impulse response in discrete time is
the familiar triangular shape. So in this case, for
n equal to four, it will be a triangle that goes from minus three to
plus three, like so. We also remember that to obtain this triangular
characteristic, all we need to do is to convolve two zero-order hold impulse
responses of half the length. This helps us find
the frequency response of the first-order
interpolator in discrete time, which in magnitude, is the square magnitude
of a zero-order hold. So what you have, is the same general shape
of the zero-order hold, but with a steeper
low-pass characteristic, due to the fact that the frequency response is
raised to the second power. Let's look at what happens
in the frequency domain. Remember, this is the spectrum
of the original sequence shown with explicit periodicity
in the second panel, and this is the spectrum of the standard upsample sequence
where we introduce zeros. Now, when we convolve with the discrete time
interpolator, we are multiplying
the spectrum of the upsample sequence with the frequency response
of the interpolator. In the case of
the zero-order hold, we have a bland low-pass
characteristics, that will make the signals
smoother in the time domain, and will almost remove the copies of the spectrum
in the frequency domain. This is probably not
entirely acceptable, so we move on to the first-order
interpolator in most cases, and we will have
a higher rejection of the high frequency component. It is exactly the same problem
as interpolation in the continuous time domain
except that here we're working entirely in
the discrete time domain. In the limit, if we would like to have a perfect rejection of the extra copies of
the spectrum that are brought into
minus pi pi interval, we should use
an ideal low-pass with a cutoff frequency of pi over capital N. This means that the ideal digital interpolator is composed of two elements, an upsampler by capital N, where we insert zeros in
the original sequence, and an ideal low-pass filter with an impulse response
that is a sinc. Of course we cannot
achieve this in practice, but what we can do, is use as good as
an approximation as possible to the ideal low-pass
with cutoff frequency, pi over n. This is our digital
interpolator that will increase the underlying
sampling frequency of a discrete time sequence entirely in discrete time domain. This is a discrete time filter.